package ai.zixing.mashibing.new_class.class07;

import java.util.ArrayList;
import java.util.List;

// https://leetcode.cn/problems/path-sum-ii
// 收集达标路径和
public class Code04_PathSumII {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        process(root, path, 0, targetSum, ans);
        return ans;
    }

    public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
        if (x.left == null && x.right == null) {
            if (preSum + x.val == sum) {
                path.add(x.val);
                // 重新构建一个数组添加到最终集合【path还会用到，保证path的变动】
                ans.add(new ArrayList<>(path));
                // 回滚 path.add(x.val);
                path.remove(path.size() - 1);
            }
            return;
        }
        // x 的非叶子节点
        path.add(x.val);
        preSum += x.val;
        if (x.left != null) {
            process(x.left, path, preSum, sum, ans);
        }
        if (x.right != null) {
            process(x.right, path, preSum, sum, ans);
        }
        path.remove(path.size() - 1);
    }

}
